/* -------------------------------------------------------------------------------

This code is based on source provided under the terms of the Id Software 
LIMITED USE SOFTWARE LICENSE AGREEMENT, a copy of which is included with the
GtkRadiant sources (see LICENSE_ID). If you did not receive a copy of 
LICENSE_ID, please contact Id Software immediately at info@idsoftware.com.

All changes and additions to the original source which have been developed by
other contributors (see CONTRIBUTORS) are provided under the terms of the
license the contributors choose (see LICENSE), to the extent permitted by the
LICENSE_ID. If you did not receive a copy of the contributor license,
please contact the GtkRadiant maintainers at info@gtkradiant.com immediately.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY
DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

----------------------------------------------------------------------------------

This code has been altered significantly from its original form, to support
several games based on the Quake III Arena engine, in the form of "Q3Map2."

------------------------------------------------------------------------------- */



/* marker */
#define FACEBSP_C



/* dependencies */
#include "q3map2.h"



int			c_faceLeafs;


/*
================
AllocBspFace
================
*/
face_t	*AllocBspFace( void ) {
	face_t	*f;

	f = safe_malloc(sizeof(*f));
	memset( f, 0, sizeof(*f) );

	return f;
}



/*
================
FreeBspFace
================
*/
void	FreeBspFace( face_t *f ) {
	if ( f->w ) {
		FreeWinding( f->w );
	}
	free( f );
}



//This isn't right but I'm just hacking. 27
static float GetSurfaceAreaOfWinding(winding_t* Winding)
{
   float total=0;
   int j;
   //Gather the points of a triangle
   for (j=0;j<Winding->numpoints-2;j++)
   {
      vec3_t *tri[3];
      vec3_t SideA;
      vec3_t SideB;

      tri[0]=&Winding->p[0+j];
      tri[1]=&Winding->p[1+j];
      tri[2]=&Winding->p[2+j];

      //Side A
      VectorSubtract(tri[0],tri[1],SideA);
      //Side B
      VectorSubtract(tri[0],tri[2],SideB);
      
      total+= (VectorLength(SideA)*VectorLength(SideB))/2;
   }

   return 0;
}

/*
SelectSplitPlaneNum()
finds the best split plane for this node
*/

static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags )
{
	face_t		*split;
	face_t		*check;
	face_t		*bestSplit;
	int			splits, facing, front, back;
	int			side;
	plane_t		*plane;
	int			value, bestValue;
	int			i;
	vec3_t		normal;
	float		dist;
	int			planenum;
   float       sizeBias;

   int frontC,backC,splitsC,facingC;
	
	
	/* ydnar: set some defaults */
	*splitPlaneNum = -1; /* leaf */
	*compileFlags = 0;
	
	/* ydnar 2002-06-24: changed this to split on z-axis as well */
	/* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */
	
	/* if it is crossing a block boundary, force a split */
	for( i = 0; i < 3; i++ )
	{
		if( blockSize[ i ] <= 0 )
			continue;
		dist = blockSize[ i ] * (floor( node->mins[ i ] / blockSize[ i ] ) + 1);
		if( node->maxs[ i ] > dist )
		{
			VectorClear( normal );
			normal[ i ] = 1;
			planenum = FindFloatPlane( normal, dist, 0, NULL );
			*splitPlaneNum = planenum;
			return;
		}
	}
	
	/* pick one of the face planes */
	bestValue = -99999;
	bestSplit = list;

   
	for( split = list; split; split = split->next )
		split->checked = qfalse; //we don't add planes that already exist in the bsp. This stops us from checking them repeatedly

  
	for( split = list; split; split = split->next )
	{
		if ( split->checked )
			continue;
		

		plane = &mapplanes[ split->planenum ];

		splits = 0;
		facing = 0;
		front = 0;
		back = 0;
		for ( check = list ; check ; check = check->next ) 
      {
			if ( check->planenum == split->planenum ) 
         {
				facing++;
				check->checked = qtrue;	// won't need to test this plane again
				continue;
			}
			side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
			if ( side == SIDE_CROSS ) {
				splits++;
			} else if ( side == SIDE_FRONT ) {
				front++;
			} else if ( side == SIDE_BACK ) {
				back++;
			}
		}
      //Bigger is better
      sizeBias=GetSurfaceAreaOfWinding(split->w);


      //Base score = 20000 perfectly balanced 
      value = 20000-(abs(front-back));
      value -= plane->counter;// If we've already used this plane sometime in the past try not to use it again 
      value -= facing ;       // if we're going to have alot of other surfs use this plane, we want to get it in quickly.
      value -= splits*5;        //more splits = bad
		value +=  sizeBias*10; //We want a huge score bias based on plane size

/*
      //164fps - strange drops in places
      //Base score = 20000 perfectly balanced 
      value = 20000-(abs(front-back));
      value -= plane->counter*10;// If we've already used this plane sometime in the past try not to use it again 
      value -= facing ;       // if we're going to have alot of other surfs use this plane, we want to get it in quickly.
      value -= splits;        //more splits = bad
		value +=  sizeBias*10; //We want a huge score bias based on plane size
*/

 /*   //166 fps
         
      //Base score = 20000 perfectly balanced 
      value = 20000-(abs(front-back));
      value -= plane->counter;// If we've already used this plane sometime in the past try not to use it again 
      value -= facing ;       // if we're going to have alot of other surfs use this plane, we want to get it in quickly.
      value -= splits;        //more splits = bad
		value +=  sizeBias*10; //We want a huge score bias based on plane size
*/

   /*
      //150fps
      sizeBias=GetSurfaceAreaOfWinding(split->w);
      //Base score = 20000 perfectly balanced 
      value = 20000-(abs(front-back));
      value -= facing ;       // if we're going to have alot of other surfs use this plane, we want to get it in quickly.
		value +=  sizeBias*10; //We want a huge score bias based on plane size

  */


		//if ( plane->type < 3 ) {
		//	value+=5;		// axial is better
		//}
		value += split->priority;		// prioritize hints higher

		if ( value > bestValue )
      {
			bestValue = value;
			bestSplit = split;

         frontC=front;
         backC=back;
         splitsC=splits;
         facingC=facing;
		}
	}


   /*
	for( split = list; split; split = split->next )
	{
		if ( split->checked )
			continue;
		
		plane = &mapplanes[ split->planenum ];
		splits = 0;
		facing = 0;
		front = 0;
		back = 0;
		for ( check = list ; check ; check = check->next ) {
			if ( check->planenum == split->planenum ) {
				facing++;
				check->checked = qtrue;	// won't need to test this plane again
				continue;
			}
			side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
			if ( side == SIDE_CROSS ) {
				splits++;
			} else if ( side == SIDE_FRONT ) {
				front++;
			} else if ( side == SIDE_BACK ) {
				back++;
			}
		}
		value =  5*facing - 5*splits; // - abs(front-back);
		if ( plane->type < 3 ) {
			value+=5;		// axial is better
		}
		value += split->priority;		// prioritize hints higher

		if ( value > bestValue ) {
			bestValue = value;
			bestSplit = split;

         frontC=front;
         backC=back;
         splitsC=splits;
		}
	}
   */
	
	/* nothing, we have a leaf */
	if( bestValue == -99999 )
		return;
	
   //Sys_FPrintf (SYS_VRB, "F: %d B:%d S:%d FA:%ds\n",frontC,backC,splitsC,facingC );

  // if (frontC+backC<10) 
   {
    //  Sys_FPrintf (SYS_VRB, "Forced Leaf\n");
    //  return; //Test!
   }

	/* set best split data */
   
	*splitPlaneNum = bestSplit->planenum;
	*compileFlags = bestSplit->compileFlags;

   if (*splitPlaneNum>-1) mapplanes[ *splitPlaneNum ].counter++;

   }



/*
CountFaceList()
counts bsp faces in the linked list
*/

int	CountFaceList( face_t *list )
{
	int		c;
	

	c = 0;
	for(list; list != NULL; list = list->next)
		c++;
	return c;
}



/*
BuildFaceTree_r()
recursively builds the bsp, splitting on face planes
*/

void BuildFaceTree_r( node_t *node, face_t *list )
{
	face_t		*split;
	face_t		*next;
	int			side;
	plane_t		*plane;
	face_t		*newFace;
	face_t		*childLists[2];
	winding_t	*frontWinding, *backWinding;
	int			i;
	int			splitPlaneNum, compileFlags;
	
	
	/* count faces left */
	i = CountFaceList( list );
	
	/* select the best split plane */
	SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
	
	/* if we don't have any more faces, this is a node */
	if ( splitPlaneNum == -1 )
	{
		node->planenum = PLANENUM_LEAF;
		c_faceLeafs++;
		return;
	}
	
	/* partition the list */
	node->planenum = splitPlaneNum;
	node->compileFlags = compileFlags;
	plane = &mapplanes[ splitPlaneNum ];
	childLists[0] = NULL;
	childLists[1] = NULL;
	for( split = list; split; split = next )
	{
		/* set next */
		next = split->next;
		
		/* don't split by identical plane */
		if( split->planenum == node->planenum )
		{
			FreeBspFace( split );
			continue;
		}
		
		/* determine which side the face falls on */
		side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
		
		/* switch on side */
		if( side == SIDE_CROSS )
		{
			ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
				&frontWinding, &backWinding );
			if( frontWinding ) {
				newFace = AllocBspFace();
				newFace->w = frontWinding;
				newFace->next = childLists[0];
				newFace->planenum = split->planenum;
				newFace->priority = split->priority;
				newFace->compileFlags = split->compileFlags;
				childLists[0] = newFace;
			}
			if( backWinding ) {
				newFace = AllocBspFace();
				newFace->w = backWinding;
				newFace->next = childLists[1];
				newFace->planenum = split->planenum;
				newFace->priority = split->priority;
				newFace->compileFlags = split->compileFlags;
				childLists[1] = newFace;
			}
			FreeBspFace( split );
		} else if ( side == SIDE_FRONT ) {
			split->next = childLists[0];
			childLists[0] = split;
		} else if ( side == SIDE_BACK ) {
			split->next = childLists[1];
			childLists[1] = split;
		}
	}


	// recursively process children
	for ( i = 0 ; i < 2 ; i++ ) {
		node->children[i] = AllocNode();
		node->children[i]->parent = node;
		VectorCopy( node->mins, node->children[i]->mins );
		VectorCopy( node->maxs, node->children[i]->maxs );
	}

	for ( i = 0 ; i < 3 ; i++ ) {
		if ( plane->normal[i] == 1 ) {
			node->children[0]->mins[i] = plane->dist;
			node->children[1]->maxs[i] = plane->dist;
			break;
		}
	}

	for ( i = 0 ; i < 2 ; i++ ) {
		BuildFaceTree_r ( node->children[i], childLists[i]);
	}
}


/*
================
FaceBSP

List will be freed before returning
================
*/
tree_t *FaceBSP( face_t *list ) {
	tree_t		*tree;
	face_t	*face;
	int			i;
	int			count;

	Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" );

	tree = AllocTree ();

	count = 0;
	for( face = list; face != NULL; face = face->next )
	{
		count++;
		for( i = 0; i < face->w->numpoints; i++ )
		{
			AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
		}
	}
	Sys_FPrintf( SYS_VRB, "%9d faces\n", count );

   for( i = 0; i < nummapplanes; i++)
   {
      mapplanes[ i ].counter=0;
   }

	tree->headnode = AllocNode();
	VectorCopy( tree->mins, tree->headnode->mins );
	VectorCopy( tree->maxs, tree->headnode->maxs );
	c_faceLeafs = 0;

	BuildFaceTree_r ( tree->headnode, list );

	Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );

	return tree;
}



/*
MakeStructuralBSPFaceList()
get structural brush faces
*/

face_t *MakeStructuralBSPFaceList( brush_t *list )
{
	brush_t		*b;
	int			i;
	side_t		*s;
	winding_t	*w;
	face_t		*f, *flist;
	
	
	flist = NULL;
	for( b = list; b != NULL; b = b->next )
	{
		if( b->detail )
			continue;
		
		for( i = 0; i < b->numsides; i++ )
		{
			/* get side and winding */
			s = &b->sides[ i ];
			w = s->winding;
			if( w == NULL )
				continue;
			
			/* ydnar: skip certain faces */
			if( s->compileFlags & C_SKIP )
				continue;
			
			/* allocate a face */
			f = AllocBspFace();
			f->w = CopyWinding( w );
			f->planenum = s->planenum & ~1;
			f->compileFlags = s->compileFlags;	/* ydnar */
			
			/* ydnar: set priority */
			f->priority = 0;
			if( f->compileFlags & C_HINT )
				f->priority += HINT_PRIORITY;
			if( f->compileFlags & C_ANTIPORTAL )
				f->priority += ANTIPORTAL_PRIORITY;
			if( f->compileFlags & C_AREAPORTAL )
				f->priority += AREAPORTAL_PRIORITY;
			
			/* get next face */
			f->next = flist;
			flist = f;
		}
	}
	
	return flist;
}



/*
MakeVisibleBSPFaceList()
get visible brush faces
*/

face_t *MakeVisibleBSPFaceList( brush_t *list )
{
	brush_t		*b;
	int			i;
	side_t		*s;
	winding_t	*w;
	face_t		*f, *flist;
	
	
	flist = NULL;
	for( b = list; b != NULL; b = b->next )
	{
		if( b->detail )
			continue;
		
		for( i = 0; i < b->numsides; i++ )
		{
			/* get side and winding */
			s = &b->sides[ i ];
			w = s->visibleHull;
			if( w == NULL )
				continue;
			
			/* ydnar: skip certain faces */
			if( s->compileFlags & C_SKIP )
				continue;
			
			/* allocate a face */
			f = AllocBspFace();
			f->w = CopyWinding( w );
			f->planenum = s->planenum & ~1;
			f->compileFlags = s->compileFlags;	/* ydnar */
			
			/* ydnar: set priority */
			f->priority = 0;
			if( f->compileFlags & C_HINT )
				f->priority += HINT_PRIORITY;
			if( f->compileFlags & C_ANTIPORTAL )
				f->priority += ANTIPORTAL_PRIORITY;
			if( f->compileFlags & C_AREAPORTAL )
				f->priority += AREAPORTAL_PRIORITY;
			
			/* get next face */
			f->next = flist;
			flist = f;
		}
	}
	
	return flist;
}

